Abstract
We consider the problem of learning and using predictions for warm startalgorithms with predictions. In this setting, an algorithm is given an instanceof a problem, and a prediction of the solution. The runtime of the algorithm isbounded by the distance from the predicted solution to the true solution of theinstance. Previous work has shown that when instances are drawn iid from somedistribution, it is possible to learn an approximately optimal fixed prediction(Dinitz et al, NeurIPS 2021), and in the adversarial online case, it ispossible to compete with the best fixed prediction in hindsight (Khodak et al,NeurIPS 2022). In this work we give competitive guarantees against stronger benchmarks thatconsider a set of $k$ predictions $\mathbf{P}$. That is, the "optimal offlinecost" to solve an instance with respect to $\mathbf{P}$ is the distance fromthe true solution to the closest member of $\mathbf{P}$. This is analogous tothe $k$-medians objective function. In the distributional setting, we show asimple strategy that incurs cost that is at most an $O(k)$ factor worse thanthe optimal offline cost. We then show a way to leverage learnable coarseinformation, in the form of partitions of the instance space into groups of"similar" instances, that allows us to potentially avoid this $O(k)$ factor. Finally, we consider an online version of the problem, where we competeagainst offline strategies that are allowed to maintain a moving set of $k$predictions or "trajectories," and are charged for how much the predictionsmove. We give an algorithm that does at most $O(k^4 \ln^2 k)$ times as muchwork as any offline strategy of $k$ trajectories. This algorithm isdeterministic (robust to an adaptive adversary), and oblivious to the settingof $k$. Thus the guarantee holds for all $k$ simultaneously.